#include <string>
#include <vector>
#include <array>
#include <unordered_map>
#include <algorithm>
#include <limits>
#include <stack>
#include <iostream>
#include <sstream>
#include <deque>
#include <queue>
#include <set>
#include <unordered_set>
#define MOD 1000000007
//     s-1
// s-2  s
//
class Solution
{
public:
    bool isInterleave1(string s1, string s2, string s3)
    {
        int n = s1.size();
        int m = s2.size();
        int s = s3.size();
        if (n + m != s)
            return false;
        std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(m + 1, false));

        dp[0][0] = true;
        for (int i = 1; i <= n; i++)
        {
            if (s1[i - 1] == s3[i - 1])
                dp[i][0] = true;
            else
                break;
        }
        for (int j = 1; j <= m; j++)
        {
            if (s2[j - 1] == s3[j - 1])
                dp[0][j] = true;
            else
                break;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (s1[i - 1] == s3[i + j - 1])
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                if (s2[j - 1] == s3[i + j - 1])
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
        }
        return dp[n][m];
    }

    bool isInterleave(string s1, string s2, string s3)
    {
        int n = s1.size();
        int m = s2.size();
        int s = s3.size();
        if (n + m != s)
            return false;
        std::vector<bool> dp(m + 1,false);

        dp[0]= true;
        for (int j = 1; j <= m; j++)
        {
            if (s2[j - 1] == s3[j - 1])
                dp[j] = true;
            else
                break;
        }
       
        for (int i = 1; i <= n; i++)
        {
            dp[0] = dp[0] && (s1[i-1] == s3[i-1]);
           for (int j = m; j >= 1; j--) {
                bool temp = false;
                // 新增：处理来自s1的字符匹配
                if (s1[i-1] == s3[i+j-1]) {
                    temp = dp[j]; // 等价于二维dp[i-1][j]
                }
                // 保留：处理来自s2的字符匹配
                if (s2[j-1] == s3[i+j-1]) {
                    temp = temp || dp[j-1]; // 等价于二维dp[i][j-1]
                }
                dp[j] = temp;
            }
        }
        return dp[m];
    }

};